from cmath import inf
from typing import List

# Floyd 模板题
class Graph:
    # 初始化
    def __init__(self, n: int, edges: List[List[int]]):
        # 数组f 表示 i 到 j 的最短路径
        self.f = [[inf] * n for _ in range(n)]

        # 每个点到自己的距离为 0
        for i in range(n):
            self.f[i][i] = 0
        # 遍历 所有的边，将边的权重信息更新到f数组中
        for u, v, w in edges:
            self.f[u][v] = w

        for k in range(n):
            for i in range(n):
                # 如果 i 到 k 没有路径，跳过本次循环
                # if self.f[i][k] == inf:
                #     continue
                for j in range(n):
                    # 更新 i 到 j 的最短路径长度
                    self.f[i][j] = min(self.f[i][j], self.f[i][k] + self.f[k][j])

    # 增加一条边
    def addEdge(self, edge: List[int]) -> None:
        f = self.f
        x, y, w = edge
        # 如果新添的权重 大于 当前x到y的最短路径，无需更新
        if w >= f[x][y]:
            return
        n = len(f)
        for i in range(n):
            for j in range(n):
                # 考虑通过新边（x,y） 来更新 i 到 j 的最短路径
                # 新边区间
                # i ----x--y ----j
                f[i][j] = min(f[i][j], f[i][x] + w + f[y][j])

    # 查询 x 到 y 的最短路径
    def shortestPath(self, node1: int, node2: int) -> int:
        ans = self.f[node1][node2]
        return ans if ans < inf else -1
# Your Graph object will be instantiated and called as such:
# obj = Graph(n, edges)
# obj.addEdge(edge)
# param_2 = obj.shortestPath(node1,node2)